package Array.easy;

/**
 * 1. 问题描述
 *      给你一个以行程长度编码压缩的整数列表nums。
 *      考虑每对相邻的两个元素[freq,val]=[nums[2*i],nums[2*i+1]]（其中i>=0），
 *      每一对都表示解压后子列表中有 freq个值为val的元素，你需要从左到右连接所有子列表以生成解压后的列表。
 *      请你返回解压后的列表。
 *
 * 2. 算法分析
 *      1. 暴力法 按照题意写就行
 *
 *      2. 优化
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 解压缩编码列表 {
    // 暴力法  时间复杂度为O(n^2) 实际上为n为n/2，只不过常数不影响阶
    public int[] decompressRLElist1(int[] nums) {
        int n = nums.length;
        int resLen = 0; // 记录结果数组的长度
        for(int i = 0; i < n; i += 2) {
            resLen += nums[i];
        }
        int[] res = new int[resLen]; // 存放最终的解压之后的数组
        int index = 0;
        for(int i = 1; i < n; i += 2) {
            for(int j = 0; j < nums[i-1]; j++) {
                res[index] = nums[i];
                index++;
            }
        }
        return res;
    }

    // 优化:考虑res数组的索引和对应nums数组中元素之间的关系，从而将时间复杂度优化为O(n)级别的
    public int[] decompressRLElist2(int[] nums) {
        int n = nums.length;
        int resLen = 0; // 记录结果数组的长度
        for(int i = 0; i < n; i += 2) {
            resLen += nums[i];
        }
        int[] res = new int[resLen]; // 存放最终的解压之后的数组
        for(int i = 0; i < resLen; i++) {

        }
        return res;
    }
}
